package 二分法;

import com.sun.org.apache.xpath.internal.operations.Mod;

import java.util.Arrays;

/**
 * @PackageName: 二分法    绝对差值和
 * @ClassName: LeetCode1818
 * @Author: chen jinxu
 * @Date: 2022/8/3 20:54
 * @Description: //TODO
 * 给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
 * 数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。
 * 你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
 * 在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
 *
 * |x| 定义为：
 *
 * 如果 x >= 0 ，值为 x ，或者
 * 如果 x <= 0 ，值为 -x
 * 输入：nums1 = [1,7,5], nums2 = [2,3,5]
 * 输出：3
 * 解释：有两种可能的最优方案：
 * - 将第二个元素替换为第一个元素：[1,7,5] => [1,1,5] ，或者
 * - 将第二个元素替换为第三个元素：[1,7,5] => [1,5,5]
 * 两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3
 * 
 * nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
 * 输出：0
 * 解释：nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0
 */
public class LeetCode1818 {
    public static void main(String[] args) {
        int[] num1 = {1, 7, 5};
        int[] num2 = {2, 3, 5};
        int result = minAbsoluteSumDiff(num1, num2);
        System.out.println(result);
    }
    static int mod = 1000000007;
    public static int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);
        int n = nums1.length;
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int a = nums1[i];
            int b = nums2[i];
            if (a == b) {
                // 无法找到更小的接近的数
                continue;
            }
            int x = Math.abs(a - b);
            sum += x;
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int mid = (left + right) / 2;
                if (sorted[mid] <= nums2[i]) {
                    left =  mid;
                } else {
                    right = mid - 1;
                }
            }
            int nd = Math.abs(sorted[right] - b);
            if (right + 1 < n) {
                nd = Math.min(nd, Math.abs(sorted[right + 1] - b));
            }

            if (nd < x) {
                ans =  Math.max(ans, x - nd);
            }
        }
        return (sum - ans) % mod;
    }

}
